#include "../include/eviction.h"

/**
 * 通用淘汰接口
 * @param cache 缓存
 * @return 0 成功, -1 失败
 * @note 通用淘汰接口,根据缓存策略选择合适的淘汰策略
 */
int eviction_evict(Cache* cache)
{
    // 根据缓存策略选择合适的淘汰策略，创建缓存时传入的参数，默认为LRU
    switch(cache->eviction_policy)
    {
        case EVICTION_LRU:
            return eviction_lru(cache);
        case EVICTION_LFU:
            return eviction_lfu(cache);
        case EVICTION_RANDOM:
            return eviction_random(cache);
        case EVICTION_APPROX_LRU:
            return eviction_approx_lru(cache, 10);
        default:
            return -1;
    }
}

/**
 * 随机淘汰
 * @param cache 缓存
 * @param node 节点
 * @return 0 成功, -1 失败
 * @note 随机淘汰,随机选择一个节点,删除该节点，不能使用cache_delete函数，因为存在重复查找的问题和被其他线程修改的问题
 * 所以需要手动删除节点调用destroy_cache_node函数，并更新统计信息
 */
int eviction_random(Cache* cache)
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache)   return -1;
    
    // 统计非空桶的数量和位置
    // 只读操作，不需要加锁
    int non_empty_buckets[cache->bucket_count];
    int non_empty_bucket = 0;
    // 遍历所有桶，统计非空桶的数量和位置
    for(int i = 0; i < cache->bucket_count; i++) {
        if(cache->buckets[i].head) {
            non_empty_buckets[non_empty_bucket++] = i;
        }
    }
    // 如果所有桶都为空，则返回失败
    if(non_empty_bucket == 0) {
        return -1;
    }
    // 随机选择一个非空桶，随机数获得桶的索引
    int random_bucket = non_empty_buckets[rand() % non_empty_bucket];
    //获取随机桶的锁
    pthread_mutex_lock(&cache->buckets[random_bucket].lock);
    // 获取桶的头部
    CacheNode* node = cache->buckets[random_bucket].head;
    // 如果节点为空，则返回失败
    if(!node) {
        pthread_mutex_unlock(&cache->buckets[random_bucket].lock);
        return -1;
    }
    // 遍历桶，统计节点数量
    int node_count = 0;
    while(node) {
        node_count++;
        node = node->next;
    }

    // 随机选择一个节点
    int random_node = rand() % node_count;
    // 重新遍历桶，找到随机节点及其前驱
    CacheNode* current = cache->buckets[random_bucket].head;
    CacheNode* prev = NULL;
    for(int i = 0; i < random_node; i++) {
        prev = current;
        current = current->next;
    }

    // 保存节点信息用于删除
    char* key_to_delete = strdup(current->key);
    int key_len = strlen(current->key);
    int value_len = strlen(current->value);
    
    // 删除节点
    if(prev == NULL) {
        cache->buckets[random_bucket].head = current->next;
    } else {
        prev->next = current->next;
    }
    
    // 释放内存
    destroy_cache_node(current);
    
    // 更新统计信息
    pthread_rwlock_wrlock(&cache->stats_lock);
    cache->total_nodes--;
    cache->current_memory -= key_len + value_len;
    cache->stats.evictions++;
    pthread_rwlock_unlock(&cache->stats_lock);
    
    pthread_mutex_unlock(&cache->buckets[random_bucket].lock);
    
    // 释放临时key
    free(key_to_delete);
    return 0;
}

/**
 * 最近最少使用
 * @param cache 缓存
 * @return 0 成功, -1 失败
 * @note 最近最少使用,因为数据结构为单向链表所以需要遍历两次，第一次遍历找到最近最少使用的节点，第二次遍历删除节点
 */
int eviction_lru(Cache* cache) 
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache)   return -1;
    // 初始化全局变量，用于记录最近最少使用的节点
    CacheNode* target_node = NULL;
    time_t oldest_time = time(NULL);
    int bucket_index = -1;
    // 创建前驱节点（用于记录找到的LRU节点的前驱）
    CacheNode* prev_node = NULL;

    // 遍历所有桶，找到最近最少使用的节点
    for(int i = 0; i < cache->bucket_count; i++) 
    {
        // 获取桶的锁
        pthread_mutex_lock(&cache->buckets[i].lock);
        // 获取桶的头部
        CacheNode* node = cache->buckets[i].head;
        // 如果节点为空，则解锁并跳过
        if(!node) {
            pthread_mutex_unlock(&cache->buckets[i].lock);
            continue;
        }
        // 遍历桶，找到最近最少使用的节点
        CacheNode* current_node = node;
        CacheNode* prev = NULL;
        while(current_node) {
            // 如果当前节点的访问时间小于全局变量，则更新全局变量
            if(current_node->last_access < oldest_time) 
            {
                oldest_time = current_node->last_access;
                // 更新全局变量
                target_node = current_node;
                prev_node = prev;
                bucket_index = i;
            }
            prev = current_node;
            current_node = current_node->next;
        }
        // 解锁
        pthread_mutex_unlock(&cache->buckets[i].lock);
    }
    // 如果没找到，则返回失败
    if(!target_node) return -1;

    // 如果找到最近最少使用的节点，则删除节点
    // 删除节点,不需要加锁，因为删除函数中会加锁，防止死锁
    // 这里不使用cache_delete函数，存在重复查找的问题，所以直接删除
    // cache_delete(cache, target_node->key);

    // 不会重复的删除节点
    // 找到要删除的LRU节点
    CacheBucket* bucket = &cache->buckets[bucket_index];
    pthread_mutex_lock(&bucket->lock);
    // 需要重新定位节点（因为链表结构可能被其他线程修改）
    CacheNode* current = bucket->head;
    CacheNode* prev = NULL;

    while(current && current != target_node) {
        prev = current;
        current = current->next;
    }
    // 如果没找到，则返回失败，就是节点不存在已经被删除
    if(!current) {
        pthread_mutex_unlock(&bucket->lock);
        return -1;
    }
    // 删除节点
    if(prev) {
        prev->next = current->next;
    } else {
        bucket->head = current->next;
    }
    // 更新统计信息
    int key_len = strlen(target_node->key);
    int value_len = strlen(target_node->value);
    // 释放内存
    destroy_cache_node(current);
    //更新统计信息
    pthread_rwlock_wrlock(&cache->stats_lock);
    cache->total_nodes--;
    cache->current_memory -= key_len + value_len;
    cache->stats.evictions++;
    pthread_rwlock_unlock(&cache->stats_lock);
    pthread_mutex_unlock(&bucket->lock);
    return 0;
}

/**
 * 最少使用淘汰
 * @param cache 缓存
 * @return 0 成功, -1 失败
 * @note 最少使用淘汰,找到访问次数最少的节点进行删除
 */
int eviction_lfu(Cache* cache) 
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache) return -1;
    
    // 定义局部变量，用于记录最少使用的节点
    CacheNode* target_node = NULL;
    int min_access_count = INT_MAX;
    int bucket_index = -1;
    // 创建前驱节点（用于记录找到的LFU节点的前驱）
    CacheNode* prev_node = NULL;
    // 遍历所有桶，找到最少使用的节点
    for(int i = 0; i < cache->bucket_count; i++) 
    {
        // 获取桶的锁
        pthread_mutex_lock(&cache->buckets[i].lock);
        
        // 获取桶的头部
        CacheNode* current_node = cache->buckets[i].head;
        CacheNode* prev = NULL;
        
        // 如果节点为空，则解锁并跳过
        if(!current_node) {
            pthread_mutex_unlock(&cache->buckets[i].lock);
            continue;
        }
        
        // 遍历桶，找到最少使用的节点
        while(current_node) 
        {
            // 如果当前节点的访问次数小于全局变量，则更新全局变量
            if(current_node->access_count < min_access_count) {
                min_access_count = current_node->access_count;
                target_node = current_node;
                prev_node = prev;
                bucket_index = i;
            }
            prev = current_node;
            current_node = current_node->next;
        }
        
        // 解锁
        pthread_mutex_unlock(&cache->buckets[i].lock);
    }
    
    // 如果没找到，则返回失败
    if(!target_node) return -1;

    // 如果找到最少使用的节点，则删除节点
    // 删除节点,不需要加锁，因为删除函数中会加锁，防止死锁
    // 这里不使用cache_delete函数，存在重复查找的问题，所以直接删除
    // cache_delete(cache, target_node->key);

    // 不会重复的删除节点
    // 找到要删除的LFU节点
    CacheBucket* bucket = &cache->buckets[bucket_index];
    pthread_mutex_lock(&bucket->lock);
    
    // 重新定位节点（因为链表结构可能被其他线程修改）
    CacheNode* current = bucket->head;
    CacheNode* prev = NULL;
    
    while(current && current != target_node) {
        prev = current;
        current = current->next;
    }
    
    // 如果没找到，则返回失败，就是节点不存在已经被删除
    if(!current) {
        pthread_mutex_unlock(&bucket->lock);
        return -1;
    }
    
    // 找到要删除的节点，执行删除操作
    if(prev) {
        prev->next = current->next;
    } else {
        bucket->head = current->next;
    }
    
    // 保存节点信息用于统计（在释放内存之前）
    int key_len = strlen(current->key);
    int value_len = strlen(current->value);
    
    // 释放内存
    destroy_cache_node(current);
    
    // 更新统计信息
    pthread_rwlock_wrlock(&cache->stats_lock);
    cache->total_nodes--;
    cache->current_memory -= key_len + value_len;
    cache->stats.evictions++;
    pthread_rwlock_unlock(&cache->stats_lock);
    
    pthread_mutex_unlock(&bucket->lock);
    
    return 0;
}

/**
 * LFU衰减
 * @param cache 缓存
 * @return 0 成功, -1 失败
 * @note LFU衰减,找到最近最少使用的节点进行衰减，衰减的值为1,让新数据有竞争机会
 */
int lfu_decay(Cache* cache)
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache) return -1;
    // 遍历所有的桶，
    for(int i = 0; i < cache->bucket_count; i++)
    {
        //获取桶
        CacheBucket* bucket = &cache->buckets[i];
        pthread_mutex_lock(&bucket->lock);
        CacheNode* current_node = bucket->head;
        while(current_node)
        {
            // 如果当前节点的访问次数大于0，则衰减
            // 如果当前节点的访问次数大于1，则衰减,防止过度衰减
            if(current_node->access_count > 1)
            {
                current_node->access_count = current_node->access_count  / 2;
            }
            current_node = current_node->next;
        }
        pthread_mutex_unlock(&bucket->lock);
    }
    return 0;
}

/**
 * LFU维护
 * @param cache 缓存
 * @return 0 成功, -1 失败
 * @note LFU维护,找到访问次数最少的节点进行维护，此函数需要在后台线程中定期调用
 */
int lfu_maintenance(Cache* cache)
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache) return -1;
    
    // 静态变量，记录上次衰减的时间（线程安全，因为只在单线程中使用）
    static time_t last_decay_time = 0;
    time_t now = time(NULL);
    // 这里设置默认衰减时间为1小时
    if(now - last_decay_time > 3600)
    {
        // 执行衰减
        lfu_decay(cache);
        // 更新上次衰减的时间
        last_decay_time = now;
    }
    return 0;
}

/**
 * 近似LRU淘汰，
 * @param cache 缓存
 * @param sample_size 采样大小
 * @return 0 成功, -1 失败
 * @note 近似LRU淘汰,随机采样部分节点，找到最近最少使用的节点进行淘汰
 * 适合大缓存，因为随机采样，不需要遍历所有节点，所以性能较好
 */
int eviction_approx_lru(Cache* cache, int sample_size)
{
    // 参数检查，如果缓存为空，则返回失败
    if(!cache) return -1;

    // 初始化局部变量
    CacheNode* target_node = NULL;
    // 用来记录最久访问的时间
    time_t oldest_time = time(NULL);
    int target_bucket = -1;
    CacheNode* prev_node = NULL;

    // 随机采样
    int sample_taken = 0;
    int max_attempts = sample_size * 3;
    int attempts = 0;
    
    while(sample_taken < sample_size && attempts < max_attempts)
    {
        attempts++;

        int bucket_index = rand() % cache->bucket_count;
        CacheBucket* bucket = &cache->buckets[bucket_index];

        // 加锁
        pthread_mutex_lock(&bucket->lock);

        // 如果桶为空，则解锁并跳过
        if(!bucket->head)
        {
            pthread_mutex_unlock(&bucket->lock);
            continue;
        }
        
        int node_count = 0;
        CacheNode* current_node = bucket->head;
        while(current_node)
        {
            node_count++;
            current_node = current_node->next;
        }
        // 如果桶为空，则解锁并跳过
        if(node_count == 0)
        {
            pthread_mutex_unlock(&bucket->lock);
            continue;
        }

        int random_node = rand() % node_count;
        current_node = bucket->head;
        CacheNode* prev = NULL;
        // 找到随机节点
        for(int i = 0; i < random_node; i++)
        {
            prev = current_node;
            current_node = current_node->next;
        }
        // 检查是否为最久未访问的节点
        if(current_node->last_access < oldest_time)
        {
            // 更新局部变量
            oldest_time = current_node->last_access;
            target_node = current_node;
            prev_node = prev;
            target_bucket = bucket_index;
        }
        // 解锁
        pthread_mutex_unlock(&bucket->lock);
        // 更新采样计数
        sample_taken++;
    }
    // 如果没找到，则返回失败
    if(!target_node) return -1;

    // 找到要删除的节点
    CacheBucket* bucket = &cache->buckets[target_bucket];
    pthread_mutex_lock(&bucket->lock);
    // 重新定位节点
    CacheNode* current = bucket->head;
    CacheNode* prev = NULL;
    while(current && current != target_node)
    {
        prev = current;
        current = current->next;
    }
    // 如果没有找到，说明已经被其他线程删除
    if(!current)    return -1;
    // 删除节点
    if(prev)
    {
        prev->next = current->next;
    }
    else 
    {
        bucket->head = current->next;
    }
    // 记录统计信息
    int key_len = strlen(current->key);
    int value_len = strlen(current->value);
    // 释放内存
    destroy_cache_node(current);
    // 更新统计信息
    pthread_rwlock_wrlock(&cache->stats_lock);
    cache->total_nodes--;
    cache->current_memory -= key_len + value_len;
    cache->stats.evictions++;
    pthread_rwlock_unlock(&cache->stats_lock);
    // 解锁
    pthread_mutex_unlock(&bucket->lock);
    return 0;
}
